import java.security.interfaces.RSAKey;
import java.util.HashMap;

import javax.swing.tree.TreeNode;

/*
 * @lc app=leetcode.cn id=337 lang=java
 *
 * [337] 打家劫舍 III
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
// class Solution {
//     //递归解法:超时了122/124
//     public int rob(TreeNode root) {
//         if(root==null) return 0;
//         int money=root.val;
//         if(root.left!=null){
//             money+=rob(root.left.left)+rob(root.left.right);
//         }
//         if(root.right!=null){
//             money+=rob(root.right.left)+rob(root.right.right);
//         }
//         //比较上面爷爷+四个孙子的钱和两个孩子的钱
//         return Math.max(money,rob(root.left)+rob(root.right));


//     }
// }

// class Solution {
//     //递归+记忆化，上面每次都计算了爷爷+四个孙子的前和两个孩子的钱，但是当孩子作为爷爷的时候，又会计算孙子的钱（此时，孙子就是它的孩子）
    
//     public int rob(TreeNode root) {
//        HashMap<TreeNode,Integer> memory=new HashMap<>();
//        return robByMemory(root,memory);

//     }
//     public int robByMemory(TreeNode root,HashMap<TreeNode,Integer> memory){
//         if(root==null) return 0;
//         if(memory.containsKey(root)) return memory.get(root);
//         int money=root.val;
//         if(root.left!=null){
//             money+=robByMemory(root.left.left, memory)+robByMemory(root.left.right, memory);
//         }
//         if(root.right!=null){
//             money+=robByMemory(root.right.left, memory)+robByMemory(root.right.right, memory);
//         }
//         int result=Math.max(money, robByMemory(root.left, memory)+robByMemory(root.right, memory));
//         memory.put(root, result);
//         return result;
//     }
// }


class Solution {
    // dp，转化为当前状态偷还是不偷时求最大偷取金额,0代表未偷，1代表偷
    public int rob(TreeNode root) {
       int[] res=robByMemory(root);
       return Math.max(res[0],res[1]);
     
    }

    public int[] robByMemory(TreeNode root){
        if(root==null) return new int[]{0,0};
        int[] res=new int[2];
        int[] left=robByMemory(root.left);
        int[] right=robByMemory(root.right);
        res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        res[1]=root.val+left[0]+right[0];
        return res;
    }
}
// @lc code=end

